|
In mathematics and computer science, the critical exponent of a finite or infinite sequence of symbols over a finite alphabet describes the largest number of times a contiguous subsequence can be repeated. For example, the critical exponent of "Mississippi" is 7/3, as it contains the string "ississi", which is of length 7 and period 3. If ''w'' is an infinite word over the alphabet ''A'' and ''x'' is a finite word over ''A'', then ''x'' is said to occur in ''w'' with exponent α, for positive real α, if there is a factor ''y'' of ''w'' with ''y'' = ''x''''a''''x''0 where ''x''0 is a prefix of ''x'', ''a'' is the integer part of α, and the length |''y''| ≥ α |''x''|: we say that ''y'' is an ''α-power''. The word ''w'' is ''α-power-free'' if it contains no factors which are α-powers.〔 p.281〕 The ''critical exponent'' for ''w'' is the supremum of the α for which ''w'' has α-powers,〔Berstel et al (2009) p.126〕 or equivalently the infimum of the α for which ''w'' is α-power-free.〔 ==Examples== * The critical exponent of the Fibonacci word is (5 + √5)/2 ≈ 3.618.〔〔 p. 37〕 * The critical exponent of the Thue–Morse sequence is 2.〔 The word contains arbitrarily long squares, but in any factor ''xxb'' the letter ''b'' is not a prefix of ''x''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Critical exponent of a word」の詳細全文を読む スポンサード リンク
|